Árbol de Expansión Mínima sujeto a restricciones de flujo

Agustín García Romero
ITESM. Paseo de la Reforma, Lomas de Cuernavaca.
Cuernavaca, Mor
E-Mail: [email protected]
http://www.mor.itesm.mx/~al374654

Marzo 1999

INSTANCIA

Un grafo G = (V,E), un vértice especificado v₀, capacidad c(e) � Z₀⁺ y longitud l(e) � Z₀⁺ para cada e � E, un requerimiento r(v) � Z₀⁺ para cada v � V-{v₀}, y un límite B � Z₀⁺.

PREGUNTA

Existe un árbol de expansión T para G tal que la suma de las longitudes de los arcos en T no exceda B y tal que para cada arco e en T, si �(e) es el conjunto de vértices para los cuales el camino hacia v₀ en T contiene e, entonces �_{u � �(c)} r(u) � c(e)?

Transformación 3SAT.¹

Es un problema NP-Completo en el sentido estricto de la palabra, aún si los requerimientos son 1 y todos las capacidades son iguales a 3.

Es posible de resolverse en tiempo polinomial por algunas técnicas de aparemiento si todos los requerimientos son 1 y todas las capacidades son igual a 2. También se puede resolver en tiempo plinomial (por algoritmos de redes de flujo de costo mínimo²) si todas las capacidades son 1 y los requerimientos son 0 o 1, y la longitud de los arcos es 0 o 1.

References

[]

''Computers and Intractability: A guide to the theory of NP-Completess'' Michael R. Garey and David S. Johnson.

Footnotes:

¹ ''The complexity of the capacitaded tree problem'' Papadimitiou, C. Report no. TR-21-76, Center for Research in Computing Technology, Harvard University, Cambridge, MA.

² ''Theoretical improvements in algorithmic efficiency for the network flow problems'' Edmonds, J. and R. M. Karp, J. Assoc. Comput. Mach 19 248-264.